package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

type Hash func(data []byte) uint32

// Map
//定义了函数类型 Hash，采取依赖注入的方式，
//允许用于替换成自定义的 Hash 函数，
//也方便测试时替换，默认为 crc32.ChecksumIEEE 算法
type Map struct {
	hash     Hash           //Hash 函数
	replicas int            //虚拟节点倍数
	keys     []int          //哈希环
	hashMap  map[int]string // 虚拟节点与真实节点的映射表
	//键是虚拟节点的哈希值，值是真实节点的名称。
}

func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}

// Add 允许传入 0 或 多个真实节点的名称
func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		// 对每一个真实节点，创建m.replicas个虚拟节点
		for i := 0; i < m.replicas; i++ {
			//虚拟节点的名称
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			//将虚拟节点添加到环上
			m.keys = append(m.keys, hash)
			m.hashMap[hash] = key
		}
	}
	sort.Ints(m.keys)
}

func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}

	// 计算 节点名称的哈希值
	hash := int(m.hash([]byte(key)))
	// 顺时针找到第一个匹配的虚拟节点的下标
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})

	return m.hashMap[m.keys[idx%len(m.keys)]]
}
